package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.LinkedList;

public class Problem152A {

	/**
	 * 1/2 = 1/x1^2 + ... + 1/xm^2
	 * x1 = 2,
	 * @param args
	 */
	public static void main(String[] args) {

		long s = System.currentTimeMillis();
		
		Q q = new Q(BigInteger.valueOf(1), BigInteger.valueOf(4));
		System.out.println(express(q, 35));
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}
	
	private static class Q implements Comparable<Q> {	//n/m

		public static Q ZERO = new Q(BigInteger.ZERO, BigInteger.ONE);
		public static Q ONE = new Q(BigInteger.ONE, BigInteger.ONE);
		
		public BigInteger n;
		public BigInteger m;
		
		public Q(Q q) {
			this.n = q.n;
			this.m = q.m;
		}
		public Q(BigInteger n, BigInteger m) {
			BigInteger d = gcd(n.abs(), m.abs());
			this.n = n.divide(d);
			this.m = m.divide(d);
		}
		
		public String toString() {
			return n + "/" + m;
		}
		
		public Q add(Q q) {
			return new Q(this.n.multiply(q.m).add(this.m.multiply(q.n)), this.m.multiply(q.m));
		}

		public Q subtract(Q q) {
			return new Q(this.n.multiply(q.m).subtract(this.m.multiply(q.n)), this.m.multiply(q.m));
		}

		public int compareTo(Q q) {
			return this.n.multiply(q.m).compareTo(this.m.multiply(q.n));
		}
		
		private BigInteger gcd(BigInteger a, BigInteger b) {
			if (a.compareTo(b) < 0) {
				return gcd(b, a);
			} else if (b.equals(BigInteger.ZERO)) {
				return a;
			} else {
				return gcd(b, a.mod(b));
			}
		}
		
		public double doubleValue() {
			return n.doubleValue()/m.doubleValue();
		}
	}
	
	public static class Stack extends LinkedList<Integer> {

		private static final long serialVersionUID = 1L;

		private Q r;

		public Stack() {
			super();
			r = new Q(BigInteger.ZERO, BigInteger.ONE);
		}
		
		@Override
		public Integer pop() {
			int m = super.pop();
			r = r.subtract(new Q(BigInteger.ONE, BigInteger.valueOf(m*m)));
			return m;
		}
		
		@Override
		public void push(Integer m) {
			super.push(m);
			r = r.add(new Q(BigInteger.ONE, BigInteger.valueOf(m*m)));
		}
		
		public String toString() {
			return super.toString() + ":" + r;
		}
		
		public String toFormulaString() {
			String s = r + " = ";
			for (int i = 0; i < this.size(); i ++) {
				if (i > 0) s += " + ";
				s += "1/" + this.get(i) + "^2";
			}
			return s;
		}
		
	}
	
	public static void moveToNext(Stack s, int max) {
		
		int m = s.pop();
		if (m < max) {
			s.push(m+1);
		} else {
			m = s.pop();
			s.push(m+1);
		}
	}
	
	public static long express(Q q, int max) {
		
		long count = 0;
		Q z = Q.ZERO;
		Q minD = new Q(BigInteger.ONE, BigInteger.valueOf(max*max));
		Stack s = new Stack();
		while (true) {
			System.out.println(s);
			if (s.isEmpty()) {
				s.push(2);
			} else {
				Q d = q.subtract(s.r);
				int c = d.compareTo(z);
				if (c == 0) {
					System.out.println(s.toFormulaString());
					count ++;
					moveToNext(s, max);
				} else if (c < 0) {
					throw new RuntimeException("NEVER GOES HERE!");
				} else {
					if (d.compareTo(minD) >= 0) {
						int m = s.peek();
						if (d.compareTo(new Q(BigInteger.ONE, BigInteger.valueOf(m))) > 0) {
							moveToNext(s, max);
						} else {
							int t = (int)Math.sqrt(d.m.doubleValue()/d.n.doubleValue());
							int n = Math.max(m+1, t+1);
							if (d.n.multiply(BigInteger.valueOf(t*t)).equals(d.m)) {
								n = Math.max(m+1, t);
							}
							if (n > max) {
								s.pop();
								moveToNext(s, max);
							} else {
								s.push(n);
							}
						}
					} else {
						moveToNext(s, max);
					}
				}
			}
		}
	}
}
